Chapter 1: Introduction. S = <{We}c<w; C,U,n,0,w> is the substructure formed by restricting the lattice <^P(w); C , U, n,0,w> to the re subsets We of the ...

We explore the interaction between Lebesgue measure and dominating functions. We show, via both a priority construction and a forcing construction, that there is a function of incomplete degree that dominates almost all degrees. This answers a question of Dobrinen and Simpson, who showed that such functions are related to the proof-theoretic strength of the regularity of Lebesgue measure for Gδ sets. Our constructions essentially settle the reverse mathematical classification of this principle.

This textbook is a second edition of the successful, Mathematical Logic: On Numbers, Sets, Structures, and Symmetry. It retains the original two parts found in the first edition, while presenting new material in the form of an added third part to the textbook. The textbook offers a slow introduction to mathematical logic, and several basic concepts of model theory, such as first-order definability, types, symmetries, and elementary extensions. Part I, Logic Sets, and Numbers, shows how mathematical logic is used to (...) develop the number structures of classical mathematics. All necessary concepts are introduced exactly as they would be in a course in mathematical logic; but are accompanied by more extensive introductory remarks and examples to motivate formal developments. The second part, Relations, Structures, Geometry, introduces several basic concepts of model theory, such as first-order definability, types, symmetries, and elementary extensions, and shows how they are used to study and classify mathematical structures. The added Part III to the book is closer to what one finds in standard introductory mathematical textbooks. Definitions, theorems, and proofs that are introduced are still preceded by remarks that motivate the material, but the exposition is more formal, and includes more advanced topics. The focus is on the notion of countable categoricity, which analyzed in detail using examples from the first two parts of the book. This textbook is suitable for graduate students in mathematical logic and set theory and will also be of interest to mathematicians who know the technical aspects of the subject, but are not familiar with its history and philosophical background. (shrink)

The paper presents an outline of the general theory of countable arithmetically saturated models of PA and some of its applications. We consider questions concerning the automorphism group of a countable recursively saturated model of PA. We prove new results concerning fixed point sets, open subgroups, and the cofinality of the automorphism group. We also prove that the standard system of a countable arithmetically saturated model of PA is determined by the lattice of its elementary substructures.

We study the proof-theoretic strength and effective content of the infinite form of Ramsey's theorem for pairs. Let RT n k denote Ramsey's theorem for k-colorings of n-element sets, and let RT $^n_{ denote (∀ k)RT n k . Our main result on computability is: For any n ≥ 2 and any computable (recursive) k-coloring of the n-element sets of natural numbers, there is an infinite homogeneous set X with X'' ≤ T 0 (n) . Let IΣ n and BΣ (...) n denote the Σ n induction and bounding schemes, respectively. Adapting the case n = 2 of the above result (where X is low 2 ) to models of arithmetic enables us to show that RCA 0 + IΣ 2 + RT 2 2 is conservative over RCA 0 + IΣ 2 for Π 1 1 statements and that $RCA_0 + I\Sigma_3 + RT^2_{ , is Π 1 1 -conservative over RCA 0 + IΣ 3 . It follows that RCA 0 + RT 2 2 does not imply BΣ 3 . In contrast, J. Hirst showed that $RCA_0 + RT^2_{ does imply BΣ 3 , and we include a proof of a slightly strengthened version of this result. It follows that $RT^2_{ is strictly stronger than RT 2 2 over RCA 0. (shrink)

The goal of this paper is to announce there is a single orbit of the c.e. sets with inclusion, ε, such that the question of membership in this orbit is ${\Sigma _1^1 }$ -complete. This result and proof have a number of nice corollaries: the Scott rank of ε is $\omega _1^{{\rm{CK}}}$ + 1; not all orbits are elementarily definable; there is no arithmetic description of all orbits of ε; for all finite α ≥ 9, there is a properly $\Delta (...) _\alpha ^0 $ orbit (from the proof). (shrink)

The paper presents four open problems concerning recursively saturated models of Peano Arithmetic. One problems concerns a possible converse to Tarski's undefinability of truth theorem. The other concern elementary cuts in countable recursively saturated models, extending automorphisms of countable recursively saturated models, and Jonsson models of PA. Some partial answers are given.

We show there is a non-recursive r.e. set A such that if W is any low r.e. set, then the join W $\oplus$ A is also low. That is, A is "almost deep". This answers a question of Jockusch. The almost deep degrees form an definable ideal in the r.e. degrees (with jump.).

We show that the double jump is definable in the computably enumerable sets. Our main result is as follows: let [Formula: see text] is the Turing degree of a [Formula: see text] set J ≥T0″}. Let [Formula: see text] such that [Formula: see text] is upward closed in [Formula: see text]. Then there is an ℒ property [Formula: see text] such that [Formula: see text] if and only if there is an A where A ≡T F and [Formula: see text]. (...) A corollary of this is that, for all n ≥ 2, the high n computably enumerable degrees are invariant in the computably enumerable sets. Our work resolves Martin's Invariance Conjecture. (shrink)

We give an examination of the automorphism group Aut of a countable recursively saturated model M of PA. The main result is a characterisation of strong elementary initial segments of M as the initial segments consisting of fixed points of automorphisms of M. As a corollary we prove that, for any consistent completion T of PA, there are recursively saturated countable models M1, M2 of T, such that Aut[ncong]Aut, as topological groups with a natural topology. Other results include a classification (...) of the normal subgroups of Aut of the form [lcub]g: g [uharr] A = idA[rcub], for sets A M, and a highly homogeneous representation of Aut as a subgroup of Aut. (shrink)

The main result of this paper is to show that for every recursive ordinal α ≠ 0 and for every nonrecursive r.e. degree d there is a r.e. set of rank α and degree d.

We state and prove the Translation Theorem. Then we apply the Translation Theorem to Soare's Extension Theorem, weakening slightly the hypothesis to yield a theorem we call the Modified Extension Theorem. We use this theorem to reprove several of the known results about orbits in the lattice of recursively enumerable sets. It is hoped that these proofs are easier to understand than the old proofs.

In this article we establish the existence of a number of new orbits in the automorphism group of the computably enumerable sets. The degree theoretical aspects of these orbits also are examined.

We introduce a tool for analysing models of $\text {CT}^-$, the compositional truth theory over Peano Arithmetic. We present a new proof of Lachlan’s theorem that the arithmetical part of models of $\text {CT}^-$ are recursively saturated. We also use this tool to provide a new proof of theorem from [8] that all models of $\text {CT}^-$ carry a partial inductive truth predicate. Finally, we construct a partial truth predicate defined for a set of formulae whose syntactic depth forms a (...) nonstandard cut which cannot be extended to a full truth predicate satisfying $\text {CT}^-$. (shrink)

Aimed at graduate students, research logicians and mathematicians, this much-awaited text covers over 40 years of work on relative classification theory for nonstandard models of arithmetic. The book covers basic isomorphism invariants: families of type realized in a model, lattices of elementary substructures and automorphism groups.

The purpose of this communication is to announce some recent results on the computably enumerable sets. There are two disjoint sets of results; the first involves invariant classes and the second involves automorphisms of the computably enumerable sets. What these results have in common is that the guts of the proofs of these theorems uses a new form of definable coding for the computably enumerable sets.We will work in the structure of the computably enumerable sets. The language is just inclusion, (...) ⊆. This structure is called ε.All sets will be computably enumerable non-computable sets and all degrees will be computably enumerable and non-computable, unless otherwise noted. Our notation and definitions are standard and follow Soare [1987]; however we will warm up with some definitions and notation issues so the reader need not consult Soare [1987]. Some historical remarks follow in Section 2.1 and throughout Section 3.We will also consider the quotient structure ε modulo the ideal of finite sets, ε*. ε* is a definable quotient structure of ε since “Χ is finite” is definable in ε; “Χ is finite” iff all subsets of Χ are computable. We use A* to denote the equivalent class of A under the ideal of finite sets. (shrink)

We observe that the classification problem for countable models of arithmetic is Borel complete. On the other hand, the classification problems for finitely generated models of arithmetic and for recursively saturated models of arithmetic are Borel; we investigate the precise complexity of each of these. Finally, we show that the classification problem for pairs of recursively saturated models and for automorphisms of a fixed recursively saturated model are Borel complete.

Let b and c be r.e. Turing degrees such that b>c. We show that there is an r.e. degree a such that b>a>c and all lattices containing a critical triple, including the lattice M5, cannot be embedded into the interval [c, a].

We show that the stabilizer of an element a of a countable recursively saturated model of arithmetic M is a maximal subgroup of Aut iff the type of a is selective. This is a point of departure for a more detailed study of the relationship between pointwise and setwise stabilizers of certain subsets of M and the types of elements in those subsets. We also show that a complete type of PA is 2-indiscernible iff it is minimal in the sense (...) of Gaifman. (shrink)

We analyze three applications of Ramsey’s Theorem for 4-tuples to infinite traceable graphs and finitely generated infinite lattices using the tools of reverse mathematics. The applications in graph theory are shown to be equivalent to Ramsey’s Theorem while the application in lattice theory is shown to be provable in the weaker system RCA0.

In recent years, mathematical logic has developed in many directions, the initial unity of its subject matter giving way to a myriad of seemingly unrelated areas. The articles collected here, which range from historical scholarship to recent research in geometric model theory, squarely address this development. These articles also connect to the diverse work of Väänänen, whose ecumenical approach to logic reflects the unity of the discipline.

We study the situation when the automorphism group of a recursively saturated structure acts on an ℝ-tree. The cases of and models of Peano Arithmetic are central in the paper.

A result of Soare and Stob asserts that for any non-recursive r.e. setC, there exists a r.e.[C] setA such thatA⊕C is not of r.e. degree. A setY is called [of]m-REA (m-REA[C] [degree] iff it is [Turing equivalent to] the result of applyingm-many iterated ‘hops’ to the empty set (toC), where a hop is any function of the formX→X ⊕W e X . The cited result is the special casem=0,n=1 of our Theorem. Form=0,1, and any (m+1)-REA setC, ifC is not ofm-REA (...) degree, then for alln there exists an-r.e.[C] setA such thatA ⊕C is not of (m+n)-REA degree. We conjecture that this holds also form≥2. (shrink)

Soare [20] proved that the maximal sets form an orbit in${\cal E}$. We consider here${\cal D}$-maximal sets, generalizations of maximal sets introduced by Herrmann and Kummer [12]. Some orbits of${\cal D}$-maximal sets are well understood, e.g., hemimaximal sets [8], but many are not. The goal of this paper is to define new invariants on computably enumerable sets and to use them to give a complete nontrivial classification of the${\cal D}$-maximal sets. Although these invariants help us to better understand the${\cal D}$-maximal (...) sets, we use them to show that several classes of${\cal D}$-maximal sets break into infinitely many orbits. (shrink)

We show that if A and $\widehat{A}$ are automorphic via Φ then the structures $S_{R}(A)$ and $S_{R}(\widehat{A})$ are $\Delta_{3}^{0}-isomorphic$ via an isomorphism Ψ induced by Φ. Then we use this result to classify completely the orbits of hhsimple sets.

A computably enumerable (c.e.) degree is a maximal contiguous degree if it is contiguous and no c.e. degree strictly above it is contiguous. We show that there are infinitely many maximal contiguous degrees. Since the contiguous degrees are definable, the class of maximal contiguous degrees provides the first example of a definable infinite anti-chain in the c.e. degrees. In addition, we show that the class of maximal contiguous degrees forms an automorphism base for the c.e. degrees and therefore for the (...) Turing degrees in general. Finally we note that the construction of a maximal contiguous degree can be modified to answer a question of Walk about the array computable degrees and a question of Li about isolated formulas. (shrink)

Soare [20] proved that the maximal sets form an orbit in${\cal E}$. We consider here${\cal D}$-maximal sets, generalizations of maximal sets introduced by Herrmann and Kummer [12]. Some orbits of${\cal D}$-maximal sets are well understood, e.g., hemimaximal sets [8], but many are not. The goal of this paper is to define new invariants on computably enumerable sets and to use them to give a complete nontrivial classification of the${\cal D}$-maximal sets. Although these invariants help us to better understand the${\cal D}$-maximal (...) sets, we use them to show that several classes of${\cal D}$-maximal sets break into infinitely many orbits. (shrink)

We prove conjectures of Herrmann and Stob by showing that the dense simple sets are orbit complete w.r.t. the simple sets.

Now in a third edition, Introduction to Philosophy: Classical and Contemporary Readings is a highly acclaimed, topically organized collection that covers five major areas of philosophy--theory of knowledge, philosophy of religion, philosophy of mind, freedom and determinism, and moral philosophy. Editor Louis P. Pojman enhances the text's topical organization by arranging the selections into a pro/con format to help students better understand opposing arguments. He also includes accessible introductions to each chapter, subsection, and individual reading, a unique feature for an (...) anthology of this depth. While the book focuses on a compelling sampling of classical material--including selections from Plato, Aristotle, Descartes, Locke, Berkeley, Hume, and Kant--it also incorporates some of philosophy's best twentieth-century and contemporary work, featuring articles by Bertrand Russell, Richard Taylor, John Searle, Thomas Nagel, and others. This third edition contains an expanded glossary, more extensive section introductions, and twelve new selections: Karl Popper: "Epistemology without a Knowing Subject" Richard Rorty: "Dismantling Truth: Solidarity Versus Objectivity" Daniel Dennett: "Postmodernism and Truth" Bruce Russell: "The Problem of Evil: Too Much Suffering" David Chalmers: "Against Materialism: Can Consciousness Be Reductively Explained?" Baron Paul Henri d'Holbach: "A Defense of Determinism" Michael Levin: "A Compatibilist Defense of Moral Responsibility" Plato: Socratic Morality: "Crito" Herodotus: "Custom Is King" J. L. Mackie: "The Subjectivity of Values" Louis P. Pojman: "A Critique of Mackie's Theory of Moral Subjectivism" Thomas Nagel: "Moral Luck". (shrink)

A model M of PA has the omega-property if it has a subset of order type omega that is coded in an elementary end extension of M. All countable recursively saturated models have the omega-property, but there are also models with the omega-property that are not recursively saturated. The papers is devoted to the study of structural properties of such models.